Some of the existing processors such as Central Processing Units (CPU) may perform the same type of operation on different data in parallel in response to one instruction called Single Instruction Multiple Data (SIMD) instruction. Such processors that execute SIMD instructions are provided with registers called SIMD registers, which store different data to be processed in parallel, in combination. For example, assume that a SIMD instruction of s1+s2 is input to a processor when data A1 and A2 are stored in a SIMD register s1 and data B1 and B2 are stored in a SIMD register s2. In this case, the processor performs two addition operations, A1+B1 and A2+B2, in parallel in response to the single instruction.
One of methods for generating code including a SIMD instruction is to search a plurality of non-SIMD instructions for two or more instructions which specify the same type of operations and are executable in parallel, and generate a SIMD instruction by combining the found instructions. For example, some of compliers that convert source code written in a high-level language into a machine-readable object code group two or more instructions into a SIMD instruction while performing an optimization process. The number of instructions that are possible to be grouped (parallelism) is different according to the architecture of a processor.
In this connection, there has been proposed a program processing method of converting source code into intermediate code written in a Register Transfer Language (RTL), extracting a set of instructions which specify the same type of operations to be applied to different data, from the intermediate code, and converting the set of instructions into a SIMD instruction. In addition, there has also been proposed a computer system which generates a trace dependency tree representing a dependency relationship among a plurality of instructions, searches the trace dependency tree for two or more instructions which are at the same level and specify the same type of operations, and merges the found instructions into a single SIMD instruction. Please see, for example, Japanese Unexamined Patent Publication No. 2003-202991 and International Publication Pamphlet No. WO2006/007193.
When generating a SIMD instruction, instructions which do not have a dependency relationship and are executable in parallel are combined. As a method of searching for such a combination of instructions, there is a method of using a tree representing a dependency relationship among instructions, as described above. When a plurality of trees (or a plurality of partial trees belonging to one big tree) is generated by analyzing code, the generated trees are compared with each other, and a combination pattern is found by combining instructions which belong to different trees and specify the same type of operations.
However, a plurality of trees generated by analyzing code may not have the same shape. Therefore, it may not be possible to find appropriate combinations of instructions only by comparing instructions at the same level as described above. Instructions at different levels may be possible to be combined. On the other hand, in order to find more combinations of instructions that are convertible into SIMD instructions, all combinations of instructions may be searched, irrespective of the tree structures. This searching, however, increases an amount of computation and causes efficiency loss.